package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

import sort.MaoPaoSort;

public class Permutation {

	public static void main(String[] args) {
		Permutation pp = new Permutation();
//		int[] nums = new int[]{1,2,1};
//		List<List<Integer>> list = pp.permuteUnique2(nums);
//		for (List<Integer> list2 : list) {
//			System.out.println(list2);
//		}
		
		int[] nums = {1, 2, 3, 4};
		pp.arrange(nums, 0);
	}
	
	//给定nums，求排列
	//nums中不含重复的元素
	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if(nums == null || nums.length <= 0){
			return result;
		}
		//同样是采用回溯的方式来做
		List<Integer> temp = new ArrayList<>();
		backtrack(result, temp, nums);
		return result;
	}
	
	int total;
	//全排列算法，交换值
	public void arrange(int[] nums , int start){
		if(start == nums.length){
			total++;
			for (int i = 0; i < nums.length; i++){
                System.out.print(nums[i] + " ");
			}
            System.out.println();
			return;
		}
		for(int i = start; i < nums.length; i++){
			MaoPaoSort.swap(nums, i, start);
			arrange(nums, start + 1);
			//复原
			MaoPaoSort.swap(nums, i, start);
		}
	}
	
	
	public void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums){
		if(temp.size() == nums.length){
			result.add(new ArrayList<>(temp));
		}
		for(int i = 0; i < nums.length; i++){
			//排列，如果已经加入了，就不再加入
			if(temp.contains(nums[i])){
				continue;
			}
			temp.add(nums[i]);
			backtrack(result, temp, nums);
			temp.remove(temp.size() - 1);
		}
	}
	
	 /**
	  * have't to see ,forgein people write clarify and explain well
     * BackTracking. 
     * If the nums array cannot be changed (i.e. cannot sort the array), than we may need to keep some thing 
     * to record which number have been used. 
     * In this question, we keep a hashmap with the numbers in the nums as the key and the number of their 
     * appearance as value
     * So each time we used a number, we substract its appearance by 1 and searching down by recursion.
     * So we only use the number with appearance greater than 0. 
     * Once we reached the length of the nums, we add current result into the ret list. 
     * And by the time the recursion returns, we backtrack by adding back 1 to the appearance and 
     * remove the last number of current result. 
     * O(n! * n) time, O(n) space with consider the recursion stack. The recursion stack
     * would consume O(n) space since the recutsion would be n-level in depth where n is the length of nums. 
     */
	//有重复的元素时，比如[1, 1, 2]
	//可是结果是超时，测试用例里面有一个8位数的，看来不能一个一个排列
	//测试用例： [-1,2,-1,2,1,-1,2,1]
	public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums == null || nums.length <= 0){
            return result;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        Integer times = 0;
        for(int i = 0; i < nums.length; i++){
            if((times = map.get(nums[i])) != null){
                map.put(nums[i], times + 1);
            }else{
                map.put(nums[i], 1);
            }
        }
        List<Integer> list = new ArrayList<Integer>();
        backtrack(result, list, nums, map);
        return result;
    }
	
	public void backtrack(List<List<Integer>> result, List<Integer> list, int[] nums, 
			HashMap<Integer, Integer> map){
//		System.out.println("size: " + list.size());
		if(list.size() == nums.length){
//			if(!result.contains(list)){
//				result.add(new ArrayList<Integer>(list));
//			}
//			and we would't judge if we already add this list
			result.add(new ArrayList<Integer>(list));
		}
		Integer times = 0;
//		这样写会TLE
//		for(int i = 0; i < nums.length; i++){
// 			//注意小于1表示没有该数字可以添加了
// 			if( (times = map.get(nums[i])) < 1 && list.contains(nums[i])){
// 				continue;
// 			}
// 			list.add(nums[i]);
// 			map.put(nums[i], times - 1);
// 			backtrack(result, list, nums, map);
// 			map.put(nums[i], times);
// 			list.remove(list.size() - 1);
// 		}
		Set<Integer> set = map.keySet();
		for (Integer integer : set) {
			//注意小于1表示没有该数字可以添加了
			//这里可以写成
			if((times = map.get(integer)) < 1 ){
				continue;
			}
//			if( (times = map.get(integer)) < 1 && list.contains(integer)){
//				continue;
//			}
			list.add(integer);
			map.put(integer, times - 1);
			backtrack(result, list, nums, map);
			map.put(integer, times);
			list.remove(list.size() - 1);
		}
	}
	
	/**
    * If we are allowed to sort the array, we could sort the array to let the same number cluster together. 
    * In this way, avoiding duplicates, which is to avoid the same number being the first number 
    * in the permutation, is simplified bacause we can judge is a number is the same as its previous one 
    * and if its previous one has been used. 
    * We keep a boolean array to store the numbers being used, whose values are false originally. 
    * Each time we use a number, we set its corresponding value in boolean array to be true. 
    * And we try further down in the recursion. 
    * Once the recursion returns, we backtrack by changing its corresponding boolean value to be false 
    * and remove it from the current result.
    * O(n!) time, O(n) space.
    */
	public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null || nums.length == 0) return ret;
        Arrays.sort(nums);
        //用于记录是否使用过
        boolean[] used = new boolean[nums.length];
        
        permuteHelper(nums, 0, ret, used, new ArrayList<Integer>());
        
        return ret;
    }
	private void permuteHelper(int[] nums, int len, List<List<Integer>> ret, 
			boolean[] used, List<Integer> curr) {
		if (len == nums.length) {
			System.out.println(curr);
			ret.add(new ArrayList<Integer>(curr));
			return;
		}
		for(int i = 0; i < nums.length; i++){
			if(!used[i]){
				System.out.println(curr);
				//注意，如果后面的与前面的相同，那我们可以不使用
				if (i > 0) {
					System.out.println("length: " + len + " i: " + i + "   " + used[i - 1]);
				}
				if(i > 0 && nums[i] == nums[i - 1] && used[i - 1]){
					continue;
				}
				used[i] = true;
				curr.add(nums[i]);
				permuteHelper(nums, len + 1, ret, used, curr);
				curr.remove(curr.size() - 1);
				used[i] = false;
			}
		}
	}
}
